home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / wtek0693.zip / OOPALLEY.ZIP / SORTCLTN.CPP < prev    next >
C/C++ Source or Header  |  1993-04-27  |  3KB  |  110 lines
  1. #include "sortcltn.h"
  2.  
  3. #define THIS    SortedCltn
  4. #define BASE    OrderedCltn
  5. DEFINE_CLASS(SortedCltn,OrderedCltn);
  6.  
  7. SortedCltn::SortedCltn(unsigned size) : OrderedCltn(size) {}
  8.  
  9. SortedCltn::SortedCltn(const SortedCltn& s) : OrderedCltn(s) {}
  10.  
  11. void SortedCltn::operator=(const SortedCltn& s)
  12. {
  13.     this->OrderedCltn::operator=(s);
  14. }
  15.  
  16. bool SortedCltn::operator==(const SortedCltn& s) const
  17. {
  18.     return this->OrderedCltn::operator==(s);
  19. }
  20.     
  21. Object* SortedCltn::add(const Object& ob)
  22. {
  23.     if (size()==0) {        // add first object to collection 
  24.         this->OrderedCltn::add(ob);
  25.         return (Object*)&ob;
  26.     }
  27. /*
  28. Do a binary search to determine where to insert the object.  This binary
  29. search algorithm was adapted from Knuth, "The Art of Computer
  30. Programming", Vol. 3, Section 6.2.1, Algorithm U.
  31. */
  32.     register int i =(size()+1)>>1;
  33.     register int m =size()>>1;
  34.     while (YES) {
  35.         if (i>0 && ob.compare(*contents[i-1])<0) {
  36.             if (m==0) {
  37.                 this->OrderedCltn::addAtIndex(i-1,ob);
  38.                 return (Object*)&ob;
  39.             }
  40.             else i -= (m+1)>>1;
  41.         }
  42.         else {
  43.             if (m==0) {
  44.                 this->OrderedCltn::addAtIndex(i,ob);
  45.                 return (Object*)&ob;
  46.             }
  47.             else i += (m+1)>>1;
  48.         m >>= 1;
  49.         }
  50.     }
  51. }
  52.     
  53. Object* SortedCltn::addAfter(const Object& ob, const Object& /*newob*/)
  54. {
  55.     shouldNotImplement("addAfter"); return (Object*)&ob;
  56. }
  57.  
  58. Object* SortedCltn::addAllLast(const OrderedCltn&)
  59. {
  60.     shouldNotImplement("addAllLast"); return (Object*)0;
  61. }
  62.  
  63. Object* SortedCltn::addBefore(const Object& ob, const Object& /*newob*/)
  64. {
  65.     shouldNotImplement("addBefore"); return (Object*)&ob;
  66. }
  67.  
  68. Object* SortedCltn::addLast(const Object& ob)
  69. {
  70.     shouldNotImplement("addLast"); return (Object*)&ob;
  71.  
  72. }
  73.  
  74. void SortedCltn::atAllPut(const Object&)
  75. {
  76.     shouldNotImplement("atAllPut");
  77. }
  78.  
  79. int SortedCltn::indexOfSubCollection(const SeqCltn& /*cltn*/,
  80.                                      int /*start*/) const
  81. {
  82.     shouldNotImplement("indexOfSubCollection"); return 0;
  83. }
  84.  
  85. //SeqCltn SortedCltn::operator&(const SeqCltn& cltn) const
  86. SeqCltn SortedCltn::operator&(/*const*/ SeqCltn& cltn) const //-gmv 5/2/90
  87. {
  88.     shouldNotImplement("operator&"); return cltn;
  89. }
  90.  
  91. void SortedCltn::replaceFrom(int /*start*/,
  92.                              int /*stop*/,
  93.                              const SeqCltn& /*replacement*/,
  94.                              int /*startAt*/)
  95. {
  96.     shouldNotImplement("replaceFrom");
  97. }
  98.  
  99. void SortedCltn::sort()
  100. {
  101.     shouldNotImplement("sort");
  102. }
  103.  
  104. SortedCltn Collection::asSortedCltn() const
  105. {
  106.     SortedCltn cltn(MAX(size(),CLTN_DEFAULT_CAPACITY));
  107.     addContentsTo(cltn);
  108.     return cltn;
  109. }
  110.